package day_2022_12_to_3.year2023;

import java.util.*;

/**
 * @author haomin
 * @date 2023/02/02 13:29
 **/
public class Day2_2_Num1129 {
    class Solution {
        public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
            List<Integer>[][] lists = new ArrayList[n][2];
            for(int[] e : redEdges){
                if(lists[e[0]][0]  == null) lists[e[0]][0] = new ArrayList<Integer>();
                lists[e[0]][0].add(e[1]);
            }
            for(int[] e : blueEdges){
                if(lists[e[0]][1]  == null) lists[e[0]][1] = new ArrayList<Integer>();
                lists[e[0]][1].add(e[1]);
            }
            int[] ans = new int[n] , flag = new int[n];
            flag[0] = 3;
            Arrays.fill(ans,-1);
            Deque<Integer> q = new ArrayDeque<>();
            q.add(0);
            int k = 0, len = 1;
            while(!q.isEmpty()) {
                int res = q.poll();
                if(ans[res] == -1) ans[res] = k;
                if((flag[res] & 2) != 0 && lists[res][0] != null){
                    for(int i : lists[res][0]){
                        if((flag[i] & 1) != 0) continue;
                        flag[i] |= (1 << 2);
                        q.add(i);
                    }
                }
                if((flag[res] & 1) != 0 && lists[res][1] != null){
                    for(int i : lists[res][1]){
                        if((flag[i] & 2) != 0) continue;
                        flag[i] |= (2 << 2);
                        q.add(i);
                    }
                }
                if(--len == 0){
                    len = q.size();
                    k++;
                    for(int i=0; i<n; i++) flag[i] = flag[i] | (flag[i] >> 2);
                }
            }
            return ans;
        }
    }
}